#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>

enum {
	true,
	false
};


//int verRepet(int* num, int M);
int geraNum(int* num, int N, int M);
void increm(int* num, int pos, int N, int M);
int posInc(int* num, int N, int M);

/*
	Tenho N posições disponíveis, para colocar M números 1
	
	__ __ __ __ __ __ __ __ : 8 posições (N)
	
	4 valores 1 (M)
	
	Colocação: 0 0 0 0 1 1 1 1
	Outra possibilidade: 0 0 0 1 0 1 1 1
	Outra possibilidade: 0 0 0 1 1 0 1 1
	
	Ou seja, encontrar as permutações de 4(M) valores iguais, em 8(N) posições.
*/

int main(void)
{
	int i;
	int ret;
	int estado;
	int a, b, c, d;
	int N = 8; /* Número de posições disponíveis */
	int M = 4; /* Quantidade de números a colocar */
	int quant = 70;
	int num[M];
	int v[M];
	int cont = 0;
	int pos;
	
	int* state;
	
	state = malloc(quant*sizeof(int));
	
	/* Inicialização */
	for ( i = 0 ; i < M ; i++ )
	{
		v[i] = i;
	}
	
	memcpy(num, v, M*sizeof(int));
	
	
// 	for ( i = 0 ; i < M ; i++ )
// 	{
// 		num[i]= v[i];
// 	}
	
	
	do {
		/* Acho que está gerando sem repetições */
		// ret = verRepet(num, M);
		
		#ifdef DEBUG1
		for ( i = 0 ; i < M ; i++ )
		{
			printf("%d\t", num[i]);
		}
		printf("\n");
		sleep(1);
		#endif
		
//		if ( ret != true )
//		{
		estado = geraNum(num, N, M);
		
		insere(l, estado);
		
		#ifdef DEBUG2
		printf("Estado = %d\n", estado);
		cont++;
		#endif
			
//		}
		
		pos = posInc(num, N, M);
		if ( pos != -1 ) increm(num, pos, N, M);
		
	} while (pos != -1);
	
	#ifdef DEBUG2
	printf("cont = %d\n", cont);
	#endif
	
	
	return 0;
}

// int verRepet(int* num, int M)
// {
// 	int i, j, cont;
// 	int tmp[M];
// 	
// 	tmp[0] = num[0];
// 	cont = 1;
// 	for ( i = 1 ; i < M ; i++ )
// 	{
// 		for ( j = 0 ; j < cont ; j++ )
// 		{
// 			if ( num[i] == tmp[j] )
// 				return true;
// 		}
// 		tmp[j] = num[i];
// 		cont++;
// 	}
// 	return false;
// }

int geraNum(int* num, int N, int M)
{
	int i;
	int estado = 0;
	for ( i = 0 ; i < M ; i++ )
	{
		estado = estado + pow(2, N-1-num[i]);
	}
	return estado;
}


int posInc(int* num, int N, int M)
{
	int i;
	int j;
	
	/* Descobrir qual posição do vetor pode ser incrementada */
	/* As M posições (0 até M-1) contém números, que vão de zero até N-1-i */
	/* Encontrar a posição que pode ser incrementada */
	
	for ( i = 0 ; i < M ; i++ )
	{
		j = M-1-i;
		if ( num[j] < (N-1-i) ) return j;
	}
	return -1;
}

void increm(int* num, int pos, int N, int M)
{
	int i;
	
	/* Incrementa o número na posição dada */
	num[pos]++;
	
	/* Todos os outros, posteriores a este seguirão uma sequencia */
	for ( i = (pos+1) ; i < M ; i++ )
	{
		num[i] = num[i-1] + 1;
	}
}